Variable length codes (VLCs) are widely used in data compression systems such as JPEG, MPEG, etc. Variable length codes are usually designed for individual syntax fields (i.e., motion vector information, transform coefficient information in video compression systems, etc.) of the bit streams, and for individual elements (i.e., individual elements of a long sequence of samples from an independently and identically distributed source) of a syntax field. When compressing an input signal, conventional approaches concatenate code words for each of the individual elements to form an output bit stream. Different code words for different syntax fields can be interleaved.
Conventional approaches have a number of drawbacks that can result in loss of compression performance. One such drawback is that restrictions imposed by syntax and semantics on the validity of code word concatenations cannot be considered in the design of each individual code table when the code tables for individual syntax elements are designed. Treating the entropy coding by concatenation of code words as a single integrated black box for performing entropy coding, the injection (or element to element mapping function) between the input data stream and the output bit stream (i.e., a “black box code book (BBXCB)”) used by the black box constitutes a VLC. The BBXCB contains code word concatenations that, even though not valid for semantic or syntactic reasons, are valid from a pure code word concatenation perspective. The existence of such code words inevitably lowers the entropy coding efficiency of the black-box.
In addition to code word concatenations that can be invalid based on syntactic and semantic constraints, a second drawback of the conventional approaches is that the possible number of code words for each code word length is regulated by the Kraft's inequality. The conventional approaches presume that no external code word or packet length information is available and, therefore, code word boundaries can only be determined based on code word design, such as a prefix condition.
It would be desirable to have a solution that uses syntactic and semantic constraints and/or side information about packet length to achieve a shorter representation of an input stream than the conventional approach.